import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2023-01-15
 * Time:18:21
 */
class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;

    public TreeNode(char val) {
        this.val = val;
    }
}

public class Test {
    public static TreeNode createTree() {
        TreeNode nodeA = new TreeNode('A');
        TreeNode nodeB = new TreeNode('B');
        TreeNode nodeC = new TreeNode('C');
        TreeNode nodeD = new TreeNode('D');
        TreeNode nodeE = new TreeNode('E');
        TreeNode nodeF = new TreeNode('F');
        TreeNode nodeG = new TreeNode('G');
        TreeNode nodeH = new TreeNode('H');
        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeC.left = nodeF;
        nodeC.right = nodeG;
        nodeE.right = nodeH;
        return nodeA;
    }

    // 前序遍历
    public static void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                System.out.println(root.val);
                stack.push(root);
                root = root.left;
            }
            if (!stack.isEmpty()) {
                root = stack.pop().right;

            }
        }
    }
    public static void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        while(!stack.isEmpty()||root!=null){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            if(!stack.isEmpty()){
                TreeNode node=stack.pop();
                System.out.println(node.val);
                root=node.right;
            }
        }
    }
    public static void postOrder(TreeNode root) {
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=null;
        TreeNode pre=null;
        stack.push(root);
        while(!stack.isEmpty()){
            cur=stack.peek();
            if((cur.left==null&&cur.right==null)||(pre!=null&&(cur.right==pre||cur.left==pre))){
                System.out.println(cur.val);
                pre=stack.pop();
            }else{
                if(cur.right!=null){
                    stack.push(cur.right);
                }
                if(cur.left!=null){
                    stack.push(cur.left);
                }

            }
        }
    }
    public static void main(String[] args) {
        TreeNode A = Test.createTree();
        //preOrder(A);
        //inOrder(A);
        postOrder(A);
    }
}
